home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / utils / diff.arc / DIFF.C < prev    next >
C/C++ Source or Header  |  1988-08-03  |  35KB  |  1,574 lines
  1. /*
  2.  * diff.c - public domain context diff program
  3.  *
  4.  */
  5.  
  6. #ifdef TURBO
  7. #include <alloc.h>
  8. #include <errno.h>
  9. #include <process.h>
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13.  
  14. #else /* !TURBO */
  15. #include <stdio.h>
  16. #include <ctype.h>
  17. #endif /* TURBO */
  18.  
  19. #ifdef atarist
  20. #define remove unlink
  21. #endif
  22.  
  23. #ifdef vms
  24. #include      <ssdef.h>
  25. #include      <stsdef.h>
  26. #define  IO_SUCCESS  (SS | STS)
  27. #define  IO_ERROR  SS
  28. #endif /* vms */
  29.  
  30. /*
  31.  * Note: IO_SUCCESS and IO_ERROR are defined in the Decus C stdio.h file
  32.  */
  33.  
  34. #ifndef  IO_SUCCESS
  35. #define  IO_SUCCESS  0
  36. #endif /* IO_SUCCESS */
  37. #ifndef  IO_ERROR
  38. #define  IO_ERROR  1
  39. #endif /* IO_ERROR */
  40.  
  41. #define  EOS      0
  42. #ifdef unix
  43. char            temfile[L_tmpnam];
  44. char           *tmpnam();
  45. #define  TEMPFILE  (temfile[0]? temfile: (tmpnam(temfile), temfile))
  46. #else /* unix */
  47. #define  TEMPFILE  "diff.tmp"
  48. #endif /* unix */
  49. #define  TRUE      1
  50. #define  FALSE      0
  51.  
  52. #ifdef  pdp11
  53. #define  short  int
  54. #endif /* pdp11 */
  55.  
  56. typedef struct candidate {
  57.     int             b;            /* Line in fileB       */
  58.     int             a;            /* Line in fileA       */
  59.     int             link;        /* Previous candidate       */
  60. } CANDIDATE;
  61.  
  62. typedef struct line {
  63.     unsigned short  hash;        /* Hash value etc.       */
  64.     short           serial;        /* Line number        */
  65. } LINE;
  66.  
  67. LINE           *file[2];        /* Hash/line for total file  */
  68. #define  fileA  file[0]
  69. #define  fileB  file[1]
  70.  
  71. LINE           *sfile[2];        /* Hash/line after prefix  */
  72. #define  sfileA  sfile[0]
  73. #define  sfileB  sfile[1]
  74.  
  75. int             len[2];            /* Actual lines in each file  */
  76. #define  lenA  len[0]
  77. #define  lenB  len[1]
  78.  
  79. int             slen[2];        /* Squished lengths       */
  80. #define  slenA  slen[0]
  81. #define  slenB  slen[1]
  82.  
  83. int             prefix;            /* Identical lines at start  */
  84. int             suffix;            /* Identical lenes at end  */
  85.  
  86. FILE           *infd[2] = {NULL, NULL};    /* Input file identifiers  */
  87. FILE           *tempfd;            /* Temp for input redirection  */
  88.  
  89. extern long     ftell();
  90. extern FILE    *fopen();
  91.  
  92. #ifdef TURBO
  93. extern void    *malloc();
  94. #else /* !TURBO */
  95. extern char    *malloc();
  96. #endif /* TURBO */
  97.  
  98. char           *fgetss();
  99. unsigned short  hash();
  100.  
  101. #ifdef    AMIGA
  102. /* Define these types for Amiga C */
  103. char           *savptr;
  104. int             savsiz;
  105. char           *wrk;
  106. char           *wrk2;
  107. int             cpysiz;
  108. #endif /* AMIGA */
  109.  
  110. /*
  111.  * The following vectors overlay the area defined by fileA
  112.  */
  113.  
  114. short          *class;            /* Unsorted line numbers  */
  115. int            *klist;            /* Index of element in clist  */
  116. CANDIDATE      *clist;            /* Storage pool for candidates  */
  117. int             clength = 0;    /* Number of active candidates  */
  118. #define    CSIZE_INC 50            /* How many to allocate each time we have to */
  119. int             csize = CSIZE_INC;        /* Current size of storage pool */
  120.  
  121. int            *match;            /* Longest subsequence       */
  122. long           *oldseek;        /* Seek position in file A  */
  123.  
  124. /*
  125.  * The following vectors overlay the area defined by fileB
  126.  */
  127.  
  128. short          *member;            /* Concatenated equiv. classes  */
  129. long           *newseek;        /* Seek position in file B  */
  130. char           *textb;            /* Input from file2 for check  */
  131.  
  132. /*
  133.  * Global variables
  134.  */
  135.  
  136. int             eflag = FALSE;    /* Edit script requested  */
  137. int             bflag = FALSE;    /* Blank supress requested  */
  138. int             cflag = FALSE;    /* Context printout       */
  139. int             iflag = FALSE;    /* Ignore case requested  */
  140. char            text[257];        /* Input line from file1  */
  141. extern char    *myalloc();        /* Storage allocator       */
  142.  
  143. extern char    *compact();        /* Storage compactor       */
  144.  
  145. #ifdef  DEBUG
  146. #ifndef OSK
  147. #define  TIMING
  148. #endif /* OSK */
  149. #endif /* DEBUG */
  150. #ifdef  TIMING
  151. extern long     time();
  152.  
  153. #ifndef atarist
  154. /* what the fuck is this??? */
  155. extern char    *4532mend;
  156. #endif
  157.  
  158. long            totaltime;
  159. long            sectiontime;
  160. char           *mstart;
  161. #endif /* TIMING */
  162. void            free();
  163. void            exit();
  164. #ifndef OSK
  165. void            perror();
  166. #endif /* OSK */
  167.  
  168. /*
  169.  * Diff main program
  170.  */
  171.  
  172. main(argc, argv)
  173.     int             argc;
  174.     char          **argv;
  175. {
  176.     register int    i;
  177.     register char  *ap;
  178.  
  179. #ifdef OSK
  180.     extern int      _memmins;
  181.     _memmins = 16 * 1024;        /* tell OSK we will malloc a lot */
  182. #endif /* OSK */
  183. #ifdef  TIMING
  184.     sectiontime = time(&totaltime);
  185. #endif /* TIMING */
  186. #ifdef vms
  187.     argc = getredirection(argc, argv);
  188. #endif /* vms */
  189.     while (argc > 1 && *(ap = argv[1]) == '-' && *++ap != EOS) {
  190.         while (*ap != EOS) {
  191.             switch ((*ap++)) {
  192.             case 'b':
  193.                 bflag++;
  194.                 break;
  195.  
  196.             case 'c':
  197.                 if (*ap > '0' && *ap <= '9')
  198.                     cflag = *ap++ - '0';
  199.                 else
  200.                     cflag = 3;
  201.                 break;
  202.  
  203.             case 'e':
  204.                 eflag++;
  205.                 break;
  206.  
  207.             case 'i':
  208.                 iflag++;
  209.                 break;
  210.  
  211.             default:
  212.                 fprintf(stderr,
  213.                         "Warning, bad option '%c'\n",
  214.                         ap[-1]);
  215.                 break;
  216.             }
  217.         }
  218.         argc--;
  219.         argv++;
  220.     }
  221.  
  222.     if (argc != 3)
  223.         error("Usage: diff [-options] file1 file2");
  224.     if (cflag && eflag) {
  225.         fprintf(stderr,
  226.                 "Warning, -c and -e are incompatible, -c supressed.\n");
  227.         cflag = FALSE;
  228.     }
  229.     argv++;
  230.     for (i = 0; i <= 1; i++) {
  231.         if (argv[i][0] == '-' && argv[i][1] == EOS) {
  232.             infd[i] = stdin;
  233.             if ((tempfd = fopen(TEMPFILE, "w")) == NULL)
  234.                 cant(TEMPFILE, "work", 1);
  235.         } else {
  236.             infd[i] = fopen(argv[i], "r");
  237.             if (!infd[i])
  238.                 cant(argv[i], "input", 2);        /* Fatal error */
  239.         }
  240.     }
  241.  
  242.     if (infd[0] == stdin && infd[1] == stdin)
  243.         error("Can't diff two things both on standard input.");
  244.  
  245.     if (infd[0] == NULL && infd[1] == NULL) {
  246.         cant(argv[0], "input", 0);
  247.         cant(argv[1], "input", 1);
  248.     }
  249. #ifdef vms
  250.     else if (infd[1] == NULL)
  251.         opendir(1, &argv[1], infd[0]);
  252.     else if (infd[0] == NULL)
  253.         opendir(0, &argv[0], infd[1]);
  254. #endif /* vms */
  255.  
  256.     /*
  257.      * Read input, building hash tables. 
  258.      */
  259.     input(0);
  260.     input(1);
  261.     squish();
  262. #ifdef  DEBUG
  263.     printf("before sort\n");
  264.     for (i = 1; i <= slenA; i++)
  265.         printf("sfileA[%d] = %6d %06o\n",
  266.                i, sfileA[i].serial, sfileA[i].hash);
  267.     for (i = 1; i <= slenB; i++)
  268.         printf("sfileB[%d] = %6d %06o\n",
  269.                i, sfileB[i].serial, sfileB[i].hash);
  270. #endif /* DEBUG */
  271.     sort(sfileA, slenA);
  272.     sort(sfileB, slenB);
  273. #ifdef  TIMING
  274.     ptime("input");
  275. #endif /* TIMING */
  276. #ifdef  DEBUG
  277.     printf("after sort\n");
  278.     for (i = 1; i <= slenA; i++)
  279.         printf("sfileA[%d] = %6d %06o\n",
  280.                i, sfileA[i].serial, sfileB[i].hash);
  281.     for (i = 1; i <= slenB; i++)
  282.         printf("sfileB[%d] = %6d %06o\n",
  283.                i, sfileB[i].serial, sfileB[i].hash);
  284. #endif /* DEBUG */
  285.  
  286.     /*
  287.      * Build equivalence classes. 
  288.      */
  289.     member = (short *) fileB;
  290.     equiv();
  291.     member = (short *) compact((char *) member, (slenB + 2) * sizeof(int),
  292.                                "squeezing member vector");
  293.  
  294.     /*
  295.      * Reorder equivalence classes into array class[] 
  296.      */
  297.     class = (short *) fileA;
  298.     unsort();
  299.     class = (short *) compact((char *) class, (slenA + 2) * sizeof(int),
  300.                               "compacting class vector");
  301. #ifdef  TIMING
  302.     ptime("equiv/unsort");
  303. #endif /* TIMING */
  304.  
  305.     /*
  306.      * Find longest subsequences 
  307.      */
  308.     klist = (int *) myalloc((slenA + 2) * sizeof(int), "klist");
  309.     clist = (CANDIDATE *) myalloc(csize * sizeof(CANDIDATE), "clist");
  310.     i = subseq();
  311. #ifndef OSK
  312.     free((char *) member);
  313.     free((char *) class);
  314. #else /* OSK */
  315.     free((char *) member - sizeof(int));
  316.     free((char *) class - sizeof(int));
  317. #endif /* OSK */
  318.     match = (int *) myalloc((lenA + 2) * sizeof(int), "match");
  319.     unravel(klist[i]);
  320. #ifndef OSK
  321.     free((char *) clist);
  322.     free((char *) klist);
  323. #else /* OSK */
  324.     free((char *) clist - sizeof(int));
  325.     free((char *) klist - sizeof(int));
  326. #endif /* OSK */
  327. #ifdef  TIMING
  328.     ptime("subsequence/unravel");
  329. #endif /* TIMING */
  330.  
  331.     /*
  332.      * Check for fortuitous matches and output differences 
  333.      */
  334.     oldseek = (long *) myalloc((lenA + 2) * sizeof(*oldseek), "oldseek");
  335.     newseek = (long *) myalloc((lenB + 2) * sizeof(*newseek), "newseek");
  336.     textb = myalloc(sizeof text, "textbuffer");
  337.     if (check(argv[0], argv[1]))
  338.         fprintf(stderr, "Spurious match, output is not optimal\n");
  339. #ifdef  TIMING
  340.     ptime